package com.atguigu.algorithm;

public class TheSmallSum {
    public static void main(String[] args) {
        int[] a=new int[]{1,3,4,2,5};
        System.out.println(findTheSmallSum(a));
    }
    //归并排序扩展问题，用归并排序巧解小和问题
    public static int findTheSmallSum(int[] a){
        return process(a,0,a.length-1);
    }
    public static int process(int[] a,int L,int R){
        if(R==L)return 0;
        int mid=L+((R-L)>>1);
        return process(a,L,mid)+process(a,mid+1,R)+merge(a,mid,L,R);
    }
    public static int merge(int[] a,int M,int L,int R){
        int[] help=new int[R-L+1];
        int p1=L;
        int p2=M+1;
        int i=0;
        int res=0;
        while(p1<=M && p2<=R){
            if(a[p1]<a[p2]){
                res+=a[p1]*(R-p2+1);
                help[i++]=a[p1++];
            }else{
                help[i++]=a[p2++];
            }
        }
        while(p1<=M){
            help[i++]=a[p1++];
        }
        while(p2<=R){
            help[i++]=a[p2++];
        }
        for(i=0;i<help.length;i++){
            a[L+i]=help[i];
        }
        return res;
    }
}
